Search results for "ACM: F.: Theory of Computation"
showing 4 items of 4 documents
Languages associated with saturated formations of groups
2013
International audience; In a previous paper, the authors have shown that Eilenberg's variety theorem can be extended to more general structures, called formations. In this paper, we give a general method to describe the languages corresponding to saturated formations of groups, which are widely studied in group theory. We recover in this way a number of known results about the languages corresponding to the classes of nilpotent groups, soluble groups and supersoluble groups. Our method also applies to new examples, like the class of groups having a Sylow tower.; Dans un article précédent, les auteurs avaient montré comment étendre le théorème des variétés d'Eilenberg à des structures plus g…
Quadratically Tight Relations for Randomized Query Complexity
2020
In this work we investigate the problem of quadratically tightly approximating the randomized query complexity of Boolean functions R(f). The certificate complexity C(f) is such a complexity measure for the zero-error randomized query complexity R0(f): C(f) ≤R0(f) ≤C(f)2. In the first part of the paper we introduce a new complexity measure, expectational certificate complexity EC(f), which is also a quadratically tight bound on R0(f): EC(f) ≤R0(f) = O(EC(f)2). For R(f), we prove that EC2/3 ≤R(f). We then prove that EC(f) ≤C(f) ≤EC(f)2 and show that there is a quadratic separation between the two, thus EC(f) gives a tighter upper bound for R0(f). The measure is also related to the fractional…
Formations of finite monoids and formal languages: Eilenberg’s variety theorem revisited
2014
International audience; We present an extension of Eilenberg's variety theorem, a well-known result connecting algebra to formal languages. We prove that there is a bijective correspondence between formations of finite monoids and certain classes of languages, the formations of languages. Our result permits to treat classes of finite monoids which are not necessarily closed under taking submonoids, contrary to the original theory. We also prove a similar result for ordered monoids.; Nous présentons une extension du théorème des variétés d'Eilenberg, un résultat célèbre reliant l'algèbre à la théorie des langages formels. Nous montrons qu'il existe une correspondance bijective entre les form…
Splicing Systems from Past to Future: Old and New Challenges
2014
A splicing system is a formal model of a recombinant behaviour of sets of double stranded DNA molecules when acted on by restriction enzymes and ligase. In this survey we will concentrate on a specific behaviour of a type of splicing systems, introduced by P\u{a}un and subsequently developed by many researchers in both linear and circular case of splicing definition. In particular, we will present recent results on this topic and how they stimulate new challenging investigations.